import java.util.HashMap;
import java.util.Map;

public class Solution677 {

    class Trie{
        int val;
        Trie[] tries=new Trie[26];
    }

    Trie root;
    Map<String,Integer> map;

    public Solution677() {
        root=new Trie();
        map=new HashMap<>();
    }

    public void insert(String key, int val) {
        int t=val-map.getOrDefault(key,0);
        map.put(key,val);
        Trie node=root;
        for (int i=0;i<key.length();i++){
            char c=key.charAt(i);
            if (node.tries[c-'a']==null){
                node.tries[c-'a']=new Trie();
            }
            node=node.tries[c-'a'];
            node.val+=t;
        }
    }

    public int sum(String prefix) {
        Trie node=root;
        for (int i=0;i<prefix.length();i++){
            char c=prefix.charAt(i);
            if (node.tries[c-'a']==null){
                return 0;
            }
            node=node.tries[c-'a'];
        }
        return node.val;
    }

    public static void main(String[] args) {
        Solution677 solution677=new Solution677();
        solution677.insert("apple",2);
        System.out.println(solution677.sum("ap"));
        solution677.insert("app",3);
        System.out.println(solution677.sum("ap"));
    }
}
